package Tree;

import java.util.Stack;

/**
 *  题目 ：二叉树剪枝
 *  题目详述 ：
 *  给定一个二叉树 根节点root，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。
 *
 * 节点 node 的子树为node 本身，以及所有 node的后代。
 *
 */
public class PruneTree {
    /**
     * 核心思想 ：
     * 即，二叉树剪枝核心思想在于判断某个节点是否为空节点，同时其左右子树上的所有节点是否也都为空
     * 解决方法 ：
     * 某个节点能否删除的条件为 ：（1）此节点自身是否为空节点；（2）此节点的左右子树是否节点都为空；
     * 使用后序遍历的话，即遍历顺序[ 左子树 ，右子树 ， 当前节点]；
     * 即，当后序遍历结束后，能够很好地判断此节点能否进行删除
     */
    // 方法一 ：递归
//    public TreeNode pruneTree(TreeNode root) {
//        // 特殊情况 ：即，二叉树的根节点为空，等价于此二叉树不存在
//        if(root == null){
//            return root;
//        }
//        // 1.遍历左子树
//        // 由于需要对于二叉树的结构进行重新构建，所有其返回值（return）为二叉树节点；
//        // 若是左子节点被删除的话，返回值为null；同时若是左子节点未被删除的话，即其返回值为原本的左子节点root.left
//        root.left = pruneTree(root.left);
//        // 2.遍历右子树
//        // 若是右子节点被删除的话，返回值为null；同时若是右子节点未被删除的话，即其返回值为原本的右子节点root.right
//        root.right = pruneTree(root.right);
//        // 某个节点能否删除的条件为 ：（1）此节点自身是否为空节点；（2）此节点的左右子树是否节点都为空；
//        // 3.若是满足节点删除的条件，则返回值为 null（空节点） 《===》 即，代表了其父节点的左子节点已经被删除
//        if(root.left == null && root.right == null && root.val == 0){
//            // 若是此节点可以被删除的话，即return值为 null；
//            return null;
//        }
//        // 4.若是为满足节点删除条件的话，即返回值仍然为root 《===》即，代表了其父节点的左子节点未被删除（还是之前的节点）
//        return root;
//    }

    // 方法二 ：迭代
    public TreeNode pruneTree(TreeNode root) {
        // 栈，用来存储父节点集合
        Stack<TreeNode> stack = new Stack<>();
        // 即，有且仅在root根节点不为null时，才会将root根节点压入stack中，初始化栈
        if(root != null){
            stack.push(root);
        }
        // 使用node节点，来存储root根节点；
        TreeNode node = root;
        // prev节点，保存上一个遍历的节点
        TreeNode prev = null;
        // 即，直到栈中为空结束循环
        while (node != null || !stack.isEmpty()){
            while (node != null){
                node = node.left;
            }
            // 若是满足一下条件，即此节点可以被删除，
            // 由于stack栈顶元素为其父节点，使得其父节点的左子节点指向null（空节点）
            if(node != null && node.val == 0 && node.right == null && node.left == null){
                stack.peek().left = null;
            }

            node = stack.peek();
            if(node.right !=null && node.right != prev){
                node = node.right;
            }
            else {
                // 此处必然是当前正在遍历节点的左子节点刚好被遍历完
                stack.pop();
                prev = node;
                node = null;
                TreeNode father = stack.peek();
                if (father.val == 0 && father.left == null && father.right == null){
                    father.right = null;
                }
            }
        }
        return root;
    }
}
